package com.loriot.common.find_missing_and_repeated_values_2965;

/**
 * @Title: Main
 * @Package: com.loriot.common.single_number_136
 * @Description:
 * @Author: zzy boy
 * @Date: 2025/10/31 9:46
 * @Version: 0.0.1-alpha
 */

public class  Main {
    class Solution {
        public int[] findMissingAndRepeatedValues(int[][] grid) {
            int n = grid.length;
            // 数进行异或操作，相同的数就会为0，位上不同就会是1
            // 两个数进行异或操作，
            int helper = 0;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    helper ^= n*i+j+1;
                    helper ^= grid[i][j];
                }
            }
            // 相当于两个结果的异或
            int lowbit = helper & -helper;//这个操作可以找到第一个为1的位
            int[] rst = new int[2];
            // 对每个数区分
            for(int[] rows : grid){
                for(int item:rows){
                    if ((item & lowbit)==0)
                        rst[0] ^= item;
                    else
                        rst[1] ^= item;
                }
            }
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid.length;j++){
                    int item = grid.length*i+j+1;
                    if ((item & lowbit)==0)
                        rst[0] ^= item;
                    else
                        rst[1] ^= item;
                }
            }
            for (int[] row : grid) {
                for (int x : row) {
                    if (x == rst[0]) {
                        return rst;
                    }
                }
            }
            return new int[]{rst[1],rst[0]};
        }
    }

    /**
     * 灵神简化方法，复杂度没有小，但是些许优化
     */
    class Solution2 {
        public int[] findMissingAndRepeatedValues(int[][] grid) {
            int n = grid.length;
            int xorAll = 0;
            for (int[] row : grid) {
                for (int x : row) {
                    xorAll ^= x;
                }
            }
            // 异或 从 1-n^2 （原理在灵神对1486的题解中）
            xorAll ^= n % 2 > 0 ? 1 : n * n;
            // 获取异或结果后面0的数量
            int shift = Integer.numberOfTrailingZeros(xorAll);

            int[] ans = new int[2];
            // 分两部分异或 1-n^2
            for (int x = 1; x <= n * n; x++) {
                ans[x >> shift & 1] ^= x;
            }
            // 分两部分异或 gird内容
            for (int[] row : grid) {
                for (int x : row) {
                    ans[x >> shift & 1] ^= x;
                }
            }
            // 通过上面异或操作之后，ans中分别有一个 ”出现两次的“ 和一个 ”缺少的“
            // 判断哪个是缺少的
            for (int[] row : grid) {
                for (int x : row) {
                    if (x == ans[0]) {
                        return ans;
                    }
                }
            }
            return new int[]{ans[1], ans[0]};
        }
    }

}
